package week_09;

/**
 * 37. 解数独
 * 编写一个程序，通过填充空格来解决数独问题。
 * <p>
 * 数独的解法需 遵循如下规则：
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 * <p>
 * <p>
 * <p>
 * 示例：
 * <p>
 * <p>
 * 输入：board = [
 * ['5','3','.','.','7','.','.','.','.'],
 * ['6','.','.','1','9','5','.','.','.'],
 * ['.','9','8','.','.','.','.','6','.'],
 * ['8','.','.','.','6','.','.','.','3'],
 * ['4','.','.','8','.','3','.','.','1'],
 * ['7','.','.','.','2','.','.','.','6'],
 * ['.','6','.','.','.','.','2','8','.'],
 * ['.','.','.','4','1','9','.','.','5'],
 * ['.','.','.','.','8','.','.','7','9']]
 * 输出：[
 * ['5','3','4','6','7','8','9','1','2'],
 * ['6','7','2','1','9','5','3','4','8'],
 * ['1','9','8','3','4','2','5','6','7'],
 * ['8','5','9','7','6','1','4','2','3'],
 * ['4','2','6','8','5','3','7','9','1'],
 * ['7','1','3','9','2','4','8','5','6'],
 * ['9','6','1','5','3','7','2','8','4'],
 * ['2','8','7','4','1','9','6','3','5'],
 * ['3','4','5','2','8','6','1','7','9']]
 * 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
 */

public class SudokuSolver_37 {
    boolean[][] rows = new boolean[9][10];
    boolean[][] cols = new boolean[9][10];
    boolean[][] box = new boolean[9][10];

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int k = board[i][j] - '0';
                    int boxid = i / 3 * 3 + j / 3;
                    rows[i][k] = true;
                    cols[j][k] = true;
                    box[boxid][k] = true;
                }
            }
        }
        search(board);
        printBoard(board);
    }

    public boolean search(char[][] board) {
        // 针对 第一个空格开始搜索
        // 开始值搜索 后 还原现场
        int[] index = firstBlank(board);
        int x = index[0];
        int y = index[1];
        if (index == null || x == -1) {
            return true;
        }
        int boxid = x / 3 * 3 + y / 3;
        for (int i = 1; i <= 9; i++) {
            if (rows[x][i] || cols[y][i] || box[boxid][i]) continue;
            board[x][y] = (char) ('0' + i);
            rows[x][i] = cols[y][i] = box[boxid][i] = true;
            if (search(board)) return true;
            board[x][y] = '.';
            rows[x][i] = cols[y][i] = box[boxid][i] = false;
        }
        return false;
    }

    public int[] firstBlank(char[][] board) {
        int[] ans = new int[]{-1, -1};
        int cnt = 10;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // 这是暴力搜索
                //if (board[i][j] == '.') return new int[]{i, j};
                // 需要优化为返回第一个 能填的合法数字最小的
                if (board[i][j] == '.') {
                    int boxid = i / 3 * 3 + j / 3;
                    int count = 0;
                    for (int k = 1; k <= 9; k++) {
                        if (!rows[i][k] && !cols[j][k] && !box[boxid][k]) count += 1;
                    }
                    if (count < cnt) {
                        cnt = count;
                        ans = new int[]{i, j};
                    }
                }
            }
        }
        return ans;
    }

    public void printBoard(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    System.out.print(board[i][j]);
                } else {
                    System.out.print(board[i][j] - '0');
                }
                System.out.print(",");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        char[][] arr = new char[][]{
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}

        };
        SudokuSolver_37 test = new SudokuSolver_37();
        test.solveSudoku(arr);

    }
}
